package demo11;

import javafx.util.Pair;

import java.util.Arrays;
import java.util.List;


class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}

public class Solution {

    //1.一和零(0-1背包)
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for(String str : strs) {
            //统计当前物品有多少各1和0
            int x = 0, y = 0;
            for(int i = 0; i < str.length(); i++) {
                if(str.charAt(i) == '0') {
                    x++;
                } else {
                    y++;
                }
            }
            //遍历背包
            for(int i = m; i >= x; i--) {
                for(int j = n; j >= y; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - x][j - y] + 1);
                }
            }
        }
        return dp[m][n];
    }

    //2.零钱兑换 II(完全背包(一维))
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for(int i = 0; i < coins.length; i++) {
            for(int j = coins[i]; j <= amount; j++) {
                dp[j] = dp[j] + dp[j - coins[i]];
            }
        }
        return dp[amount];
    }

    //3.组合总和 Ⅳ(完全背包-优化一维)
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int i = 0; i <= target; i++) {//背包
            for(int j = 0; j < nums.length; j++) {//物品
                if(i >= nums[j]) {
                    dp[i] = dp[i] + dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }

    //4.零钱兑换(动态规划！秒杀！！)
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, 10001);
        dp[0] = 0;
        for(int i = 0; i < coins.length; i++) {
            for(int j = coins[i]; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }
        }
        return dp[amount] == 10001 ? -1 : dp[amount];
    }

    //5.数组拆分(计数排序)
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for(int i = 0; i < nums.length; i += 2) {
            sum += nums[i];
        }
        return sum;
    }

    //6.完全平方数(完全背包 - 一维)
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 10001);
        dp[0] = 0;//题目并没有说要从0开始(也就是说，0不是一种方法)，所以要初始化成0
        for(int i = 1; i <= n; i++) {
            for(int j = i * i; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - i*i] + 1);
            }
        }
        return dp[n] == 10001 ? 0 : dp[n];
    }

    //7.单词拆分(完全背包 - 优化一维)
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for(int i = 1; i <= s.length(); i++) {
            for(int j = 0; j < i; j++) {
                String str = s.substring(j, i);
                if(wordDict.contains(str) && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
//
//    //8.打家劫舍
//    public int rob(int[] nums) {
//        int len = nums.length;
//        if(len == 1) {
//            return nums[0];
//        }
//        int[] dp = new int[len];
//        dp[0] = nums[0];
//        dp[1] = Math.max(nums[0], nums[1]);
//        for(int i = 2; i < len; i++) {
//            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
//        }
//        return dp[len - 1];
//    }

    //9.打家劫舍II(动态规划)
    public int rob(int[] nums) {
        int len = nums.length;
        if(len == 1) {
            return nums[0];
        }
        int a = dpRob(Arrays.copyOfRange(nums, 0, nums.length - 1));
        int b = dpRob(Arrays.copyOfRange(nums, 1, nums.length));
        return Math.max(a, b);
    }

    private int dpRob(int[] nums) {
        int len = nums.length;
        if(len == 1) {
            return nums[0];
        }
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for(int i = 2; i < len; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[len - 1];
    }

    //10.打家劫舍III(dfs+动态规划)
    public int rob(TreeNode root) {
        Pair<Integer, Integer> pair = dfs(root);
        return Math.max(pair.getKey(), pair.getValue());
    }

    private Pair<Integer, Integer> dfs(TreeNode root) {
        if(root == null) {
            return new Pair<>(0, 0);
        }
        Pair<Integer, Integer> dpLeft = dfs(root.left);
        Pair<Integer, Integer> dpRight = dfs(root.right);
        //不偷当前结点
        int val1 = Math.max(dpLeft.getKey(), dpLeft.getValue()) +
                Math.max(dpRight.getKey(), dpRight.getValue());
        //偷当前结点
        int val2 = root.val + dpLeft.getKey() + dpRight.getKey();
        Pair<Integer, Integer> dp = new Pair<>(val1, val2);
        return dp;
    }


    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 1};
        Solution solution = new Solution();
        solution.rob(arr);
    }
}

